This invention relates to a line-draw method and apparatus for generating, storing and displaying lines in a display system.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
In display systems that draw lines, each pixel (point) on the line is located and addressed by an X-axis coordinate and a Y-axis coordinate defined relative to an XY-axes system where an X-axis and an orthogonal Y-axis form a matrix of addressable pixels. A pixel is drawn by determining the X-axis and Y-axis coordinates for the pixel and a line is drawn by determining the X-axis and Y-axis coordinates for all the pixels on the line that are used to draw the line.
By way of background, a number of line-draw methods are described by Newman and Sproull in PRINCIPLES OF INTERACTIVE COMPUTER GRAPHICS, Second Edition, McGraw-Hill Book Company, 1979. One such well-known method is Bresenham's Algorithm which draws a line a pixel at a time.
The Bresenham method operates such that for each new pixel to be drawn, a new iteration of the algorithm changes one of the X-axis or Y-axis coordinate values relative to the values for the previous pixel by +1 or -1. The other coordinate value of the new pixel may or may not change, depending on the value of an error term, e. The error term represents the distance, measured perpendicular to the axis of greatest movement, between the exact path of the line and the location of the actual pixels used to draw the line.
Bresenham's method may be applied to a line with any orientation. Irrespective of how the line is actually oriented relative to the coordinate system, the Bresenham method operates essentially the same as if the line were rotated into the upper right-hand quadrant of an XY-axes system. For a line which is located in the upper right-hand quadrant of an orthogonal system and which is also positioned radially from the origin and running between the 45' line and the X-axis, then the X-axis increment of the line, .DELTA.x, changes faster than the Y-axis increment, .DELTA.y. In such an example, where the X-axis is the axis of greatest change (that is, 0.ltoreq..DELTA.y.ltoreq..DELTA.x), the error term e is measured parallel to the y axis.
Assuming an orientation where the X-axis is the axis of greatest change, each iteration of the algorithm adds the slope of the line, .DELTA.y/.DELTA.x, to the error term e. Before this addition, the sign of e is used to determine whether to increment the y coordinate of the current pixel. A positive e value indicates that the exact path of the line lies above the current pixel so that the y coordinate is incremented, and 1 is subtracted from e. If e is negative, the y coordinate value is left unchanged.
The Bresenham algorithm is expressed by the following PASCAL program of TABLE 1, which requires neither divisions nor multiplications and in which all variables are integers:
TABLE 1 ______________________________________ e: = 2 * deltay - deltax; for i: = 1 to deltax do begin Plot(x,y); if e&gt;0 then begin y: = y + 1 e: = e + (2 * deltay -2 * deltax) end else e: = e + 2 * deltay x: = x + 1 end ______________________________________
Bresenham's algorithm avoids generating duplicate pixels and also avoids multiplications and divisions so that it is well suited to implementation in either hardware or software.
When implemented in software, the Bresenham algorithm typically employs an inner loop such that X-axis and Y-axis coordinates for a single pixel are generated for every iteration of the inner loop.
An example of a typical inner loop of well-optimized Bresenham code for a Motorola 68020 processor drawing a line that is more horizontal than vertical is given in TABLE 2. Only the inner loop is shown, since the inner loop dominates performance in drawing long lines. In the display system, it is assumed that the display buffer has eight planes and is organized such that the processor can access a single pixel with a byte operation.
TABLE 2 ______________________________________ bres1: moveb d0,a0@ add a1,a0 add d2,d1 bcc bres2 add a2,a0 add d3,d1 bres2: dbra d4,bres1 ______________________________________
The Bresenham method and other line-draw methods are inefficient in that they require one test of the error term for each pixel to be generated, that is, they generate one pixel at a time. For a large number of pixels in a line, the length of time required to draw the line approaches an amount that is directly related to the number of pixels in the line. In many embodiments where line drawing speed is an important parameter of the display system, the Bresenham algorithm is too slow.
Accordingly, and in accordance with the above background, there is a need for improved line-draw methods and apparatus which are capable of improved line-draw speeds.